导语
嵌套性是网络科学的核心议题之一。近期发表在Physics Reports上的一篇论文，对复杂网络的嵌套性进行到了从现象到机制的全面综述。本文聚焦于哪些生成机制让网络在成长中获得了嵌套性。
针对这篇网络嵌套综述的更多内容，以及网络结构相关问题，我们组织了线上读书会，定期线上分享，详情与参与方式见文末。
复杂网络的嵌套性，是在生态系统、经济金融、社交网络等具体场景中都会呈现的性质。该性质和网络的鲁棒性、多样性都有所联系，在《网络嵌套结构决定公司国家命运》一文中，介绍了利用网络的嵌套性做预测的例子，本文则聚焦于哪些生成机制让网络在成长中获得了嵌套性。
论文题目：
Nestedness in complex networks: Observation, emergence, and implications
论文地址：
https://arxiv.org/abs/1905.07593
假设网络中的每个节点有一个内在属性，通常称之为节点的适应性（fitness），不同节点的适应性符合特定的概率分布，如果两个节点的适应度之和小于一个定值，称其为阈值（threshold），那么这两个节点之间就不会有连接，如果节点的适应度大于阈值，节点之间产生连接的几率符合某一概率分布，这就是阈值模型。如果节点之间的适应度的分布曲线是指数函数，那在上述的阈值模型中，产生网络呈现出在节点的度数上尺度一致性。如下图所示，图中横轴是节点的度数，纵轴是该度数节点的概率，红线是理论值，圆点是模拟下的真实情况。由于模拟的网络不是无限大的，所以左上角会偏离理论预期，而在最右边的那个点，代表在该模型下，会有极少的点，和所有的点都能产生连接。根据这个现象，如果某个节点的适应性本身就大于阈值，那么这个节点不管和谁，都有可能连接，这样的节点，就有可能成为图中最右边的那个点。在这样条件下生成的网络，节点间的连接矩阵，总会有一些节点比其他节点连接的边要多，即满足上三角的性质，从而是网络呈现出嵌套性。来源：Class ofcorrelated random networks with hidden variables在上述模型中，网络多半是无法形成全连接网络的（disassortativity），原因是对于度数为k的节点，其邻居的平均度数的分布按k^-1次衰减。用通俗的话来讲，就是大V和小V的关注者的平均节点连接数的差距，要比普通人之间更大，每个大V各自连接着一堆没什么连接的无名氏，而不是大V和小V连接，从而使得网络无法连成一个整体。阈值模型生成的网络，还有一个有趣的特性，与网络的聚类系数（cluster cofficient）有关。聚类系数衡量一个网络中的节点是否容易形成一个内部紧密联系的小团体，针对节点计算，其分母是和该节点连接的点组成的三元组（triple，三个节点形成的集合）的数量，分子是这些三元组中有多少个完全连接的三角形。下图的横轴是节点的连接数，纵轴是节点的聚类系数，当节点度数小于某个特定的值之前，网络中的聚类系数很高，这可以看成在普通人的朋友圈里，朋友的朋友也是朋友，而当你的连接超过100个，朋友的朋友相互认识的概率就会变低。
不同度数节点对应对应的聚类系数
总结阈值模型，通过引入网络在的点有不同的内在属性（适应度）这一个假设，阈值模型生成的网络能重现出现实网络中的长尾（heavy-tail），适应度要满足的分布不仅限于指数分布，高斯分布、泊松分布、logistic等分布，都可以生成和现实类似的网络。
如果网络中的节点按照一定的规则，选择对自己有利的连接，那这类的生成机制就称为自组织网络（Self-organizing network）。不管是生态系统，还是社会金融，网络中的连接都不是一成不变的，而是在不断变化、达成均衡后才相对稳定的。相比于阈值模型，自组织网络中的生成机制更加符合现实情况，也被研究得更多，有多种细分的生成模型。但这些模型都围绕着一条核心原则变化而来，即如何通过调整连接，最大化自己、自己物种以及自己所生活的群落（community）的适应度。从一个随机连接的网络起始，如果网络中的节点都嫌贫爱富，即在满足下面两个条件下随机交换一条连接：1）新增加的连接会带来一个连接数更高的邻居；2）新增加的连接不会让之前连接的节点变成孤立的。那么足够多次的连接交换之后，网络就会呈现出完美的嵌套性，且节点的度数分布呈指数函数（标度一致）。这个情景下，网络中节点最大化的是节点的度中心性（centrality），第二个条件的加入是为了避免让网络变成一个全连接的子网络与其他完全不连接的节点。现实中的网络多半不具有完美的嵌套性，这可以通过限制交换的次数来模拟。将网络中的节点分为只在类间有相互作用的两类，例如生态网络中不同的昆虫（授粉）和花，或者商业网络中的制造者和承包商，这样可以形成Mutualistic networks，如下图所示：来源：http://www.cabdyn.ox.ac.uk/complexity_PDFs/CABDyN_Seminars_2008_09/reed_tsochas_slides.pdf在mutualistic network中，有一种简单的生成机制，能够重现出真实网络中70%的性质，这个比例相比其他的生成机制，有显著的提升。该模型的假设对于上图中的鸟，同一种鸟采集对于不同果实带来的收益不同，同一种果实对不同的鸟的收益也不同，收益平均的在分布在0到1之间。生成网络时，使用两条规则：一是针对固定的动物，限定其能连接的边（采集的植物）的个数，即让每种鸟有所专精；二是根据各自的收益的相对数，决定是建立一条新的连接还是随机连接之前已连接的点。具体的数学模型参见：https://www.nature.com/articles/nature07532
这项研究有趣的是，上述的场景本是生态系统，但验证模型和现实网络符合程度时，用的却是纽约的承包商和生产者的交易网络，这展现了复杂网络研究跨学科的特性。在上面的例子中，每个鸟都是一样的，但如果将每种鸟看成一个物种，允许同一种的不同个体有所不同（吃不同的果子），那么从一个随机的网络出发，每个物种中的个体依次去掉那些给它们带来最小收益的果子，也能形成一个完美嵌套的网络。这个过程可以看成是每种鸟类去寻找一种最接近当前网络的均衡条件下，不同果子给自己种群带来收益的偏好序列，例如对自己种群最好吃的果子，有最多的鸟去吃，如此，就是前文说的优化自己群落的适应度。如下图所示，通过上述机制，从随机网络变成了具有嵌套性的网络，同时不管是授粉的昆虫还是花，都扩大了自己的种群数量，提高了适应度。
种群适应度最大化的网络演变起始点
和种群数量变化曲线
如果将视野放大，不止限于自己的种群，而是将判断是否调整连接的条件变成新的连接能否增加整个网络中总的人口，也就是说，在上述的鸟吃果子的例子中，前面要求只有在能够让本种鸟的数量增加，才改变吃的果子，现在假定只要能让所有的鸟的总数增加，哪怕自己品种的鸟吃的不好，也可以交换。在这样的机制下，同样可以生成具有嵌套结构的网络，这类似于进化理论中的群体选择。不同层级下的生成机制，导出了相同的网络性质，这说明嵌套网络的出现，是不同机制共同作用的必然结果，但具体哪种机制在起主要作用，却无法仅仅依据嵌套性本身推出。
在社交网络中，每个人都试图成为聚光灯下的焦点。在网络科学中，可以通过centrality来评价节点是否处在网络的中心。下面的模型，可以模拟社交网络中的嵌套性是如何产生的。从一个随机网络出发，随机选一个节点，以alpha的概率选择当前网络里中心性最高的未连接节点建立连接，或者以1-alpha的概率去掉当前连接中中心性最小的节点。上述机制生成的网络，不止具有嵌套性，而且按照节点度数从大到小排列，度数最大的节点的中心性也最高，度数次高的节点在中心性上排名第二，依次类推。在上述的机制下，当一个节点成为中心节点时，不是由于该节点做了什么，而应该归因于该节点是其他节点提升自己中心性的最好选择，也就是其本身的初始中心度相对较高，而上述的不同归因，可以看成是社交网络和生态网络生成机制的本质区别。上述模型中有一个关键的参数alpha，而alpha有一个关键值，这个关键值附近只要发生微小的变化，就会导致生成的网络呈现出性质上的天壤之别。读者可以思考这个alpha应该是下面的哪个：答案是第二个，也就是当网络中超过一半的人选择增加连接之后，在经过了足够多次的变化之后，网络会注定变成一个全连接的网络。下图展示的是在不同的alpha值下，网络呈现的不同情况，不同形状的点代表大小不同的网络，图中的纵轴是网络的eigenvectorcentrality。在alpha接近但不大于0.5时，生成的网络呈现完美嵌套性，且存在少数高度连接的节点，类似现实中的社交网络。引申来看，随着连接的建立越来越容易（移动互联网的普及），社交网络图图中最上面的稀疏网络，变成了最左边的相对稠密且更加中心化的形态，而由于人的精力有限，增加连接的几率不会大于删除连接的概率，因此在现有技术下无法生成图中右下角的全连接网络，至少在脑机接口成熟前不会。
不同大小的网络在模拟中
在0.5这个临界点附件呈现相同的相变特性
不同度数节点所占比例
上图横轴是节点的度数，即该节点连接的点占全部节点的比例，纵轴是该度数节点出现的概率，不同的颜色代表了不同的alpha参数。建议读者先思考一下，图中的蓝色还是黑色对应的alpha值更大。蓝色对应的是alpha为0.495，黑色对应的alpha是0.45，这幅图想说明的是度数的分布呈现出三个阶段：第一阶段相对平滑；第二阶段是指数式快速下降；第三阶段下降的趋势比较平缓。随着alpha值的提升，节点的度数需要变得比之前更大，才能突破常态，对应蓝色曲线中左边平缓的区域最长，也就是说随着alpha的增加，一个节点连接1%还是0.1%的节点，其出现的概率都是相同的，这反映到现实生活中，就是成为大V所需的初始粉丝数目，随着网络变得稠密而增加了。上述的生成机制，都是相对基础简单的模型，若想模拟现实世界，则需要更加复杂的模型。有两个具体方向：一是引入博弈机制和不完全信息，即让节点的行动不是相互独立的，节点也无法像前文社交网络中，根据网络中全部节点的信息来更新自己的连接，而只能获得局部的信息。第二个方向是在模型中让节点能够创新，在生态系统中，对应的是物种分化成多个物种，一个节点变成多个节点，在经济网络中，是节点的内在属性，比如对其他节点的连接偏好发生了变化。复杂网络的研究终极目标，是理解现实世界中，在时间和空间上都在演变的网络是否具有临界点，是否有固定的方向，演变过程中，网络的特征是怎样的。既然现实中的网络普遍具有嵌套性，那可以从通过模拟嵌套性生成的机制中，看到在网络的演化过程中，不同的性质之间如何联系并相互影响。复杂网络中的每一种性质都不是孤岛，而生成机制正是将其连接起来的桥梁。
集智嵌套网络读书会主要会组织成员一起阅读嵌套网络但不局限嵌套网络的文献、书籍，结合文献阅读，我们会在每个月组织一次集中的在线讨论，一起探讨嵌套性是如何优化网络中资源分配、信息流动以及去回答什么样的结构（组织形式）能让系统稳定增长和演化。欢迎大家参与以此为契机，加入读书会，一起交流学习，更深刻地理解自然界中的结构。
集智俱乐部QQ群｜877391004商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！